The problem can be found at the following link: Question Link
I used the Disjoint Set Union (DSU) data structure to detect cycles in an undirected graph. The steps are outlined as follows:
- Step 1: Initialize DSU data structure.
- Step 2: Iterate through each vertex in the graph.
- Step 3: For each vertex, iterate through its adjacent vertices.
- Step 4: If the current vertex and its adjacent vertex belong to the same set, there is a cycle. Merge the sets and return true.
- Step 5: If the sets are different, perform the union operation.
- Step 6: Continue the process for all vertices.
- Step 7: If a cycle is found during the process, return true. Otherwise, return false.
For a clearer explanation of the solution, please check this solution.
- Time Complexity:
O(V + E)
, whereV
is the number of vertices andE
is the number of edges. - Auxiliary Space Complexity:
O(V)
for DSU data structure.
class Solution {
public:
vector<int> dsu;
vector<bool> vis;
vector<set<int>> g;
int findDSU(int p) {
if (dsu[p] < 0)
return p;
return dsu[p] = findDSU(dsu[p]);
}
void merge(int x, int y) {
if (dsu[x] > dsu[y])
swap(x, y);
dsu[x] += dsu[y];
dsu[y] = x;
}
bool dfs(int node, int par) {
bool isCycle = false;
vis[node] = true;
for (auto child : g[node]) {
if (child != par) {
int x = findDSU(node);
int y = findDSU(child);
if (x == y)
return true;
merge(x, y);
isCycle = isCycle || dfs(child, node);
}
}
return isCycle;
}
int detectCycle(int V, vector<int> adj[]) {
dsu = vector<int>(V, -1);
vis = vector<bool>(V, false);
g = vector<set<int>>(V);
for (int i = 0; i < V; i++) {
for (auto x : adj[i])
g[i].insert(x);
}
bool isCycle = false;
for (int i = 0; i < V; i++) {
if (!vis[i])
isCycle = isCycle || dfs(i, -1);
}
return isCycle;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.